// 层序遍历:广度优先搜索（BFS）使用队列

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
function levelOrder(root) {
  if (!root) return []; // 空树直接返回

  const result = [];
  const queue = [root]; // 初始化队列，放入根节点

  while (queue.length) {
    const levelSize = queue.length; // 当前层的节点数
    const currentLevel = []; // 存储当前层的节点值

    // 处理当前层的所有节点
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift(); // 取出队列头部节点
      currentLevel.push(node.val); // 存储节点值

      // 将子节点加入队列（先左后右）
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel); // 存入当前层结果
  }

  return result;
}